package leetcode.editor.day;

import javafx.util.Pair;

import java.util.*;

// 652. 寻找重复的子树
// https://leetcode.cn/problems/find-duplicate-subtrees/
class FindDuplicateSubtrees {
    public static void main(String[] args) {
        Solution solution = new FindDuplicateSubtrees().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // 参照labuladong：https://mp.weixin.qq.com/s/LJbpo49qppIeRs-FbgjsSQ
    /*class Solution {
        LinkedList<TreeNode> res = new LinkedList<>();
        Map<String, Integer> map = new HashMap<>();

        public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
            traversal(root);
            return res;
        }

        public String traversal(TreeNode root) {
            if (root == null) return null;

            String left = traversal(root.left);
            String right = traversal(root.right);

            // 序列化来比较，必须要加,号作为分隔
            String serialize = root.val + "," + left + "," + right;

            Integer freq = map.getOrDefault(serialize, 0);
            // 防止多次重复加入，使用set会可能重复加入
            if (freq == 1) {
                res.add(root);
            }

            // 给子树对应的出现次数加一
            map.put(serialize, freq + 1);

            return serialize;
        }
    }*/

    // 方法一空间复杂度和时间复杂度O(n ^ 2)
    // 使用序列号优化，一个三元组来标识
    // 根节点的值为 x；左子树的序号为 l；右子树的序号为 r。
    // 这里的「序号」指的是：每当我们发现一棵新的子树，就给这棵子树一个序号，用来表示其结构。那么两棵树是重复的，当且仅当它们对应的三元组完全相同。
    // 序列号怎么优化？
    // 举个栗子：假如叶子节点的序列为[4,null,null]，此时他的序列号为0,那么父节点就可以表示为[1,0,null]，使用0表示左节点
    // 参照官解：https://leetcode.cn/problems/find-duplicate-subtrees/solution/xun-zhao-zhong-fu-de-zi-shu-by-leetcode-zoncw/
    class Solution {

        Map<String, Pair<TreeNode, Integer>> map = new HashMap<>();
        Set<TreeNode> set = new HashSet<>();    // 去重
        int idx = 0;  // 表示编号

        public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
            dfs(root);
            return new ArrayList<>(set);
        }

        public int dfs(TreeNode root) {
            if (root == null) return 0;
            // 三元组来标识一个节点，后序遍历
            int[] arr = new int[]{root.val, dfs(root.left), dfs(root.right)};
            // 转化为字符串存储起来
            String s = Arrays.toString(arr);
            if (map.containsKey(s)) {
                // 如果存在，返回序列号
                Pair<TreeNode, Integer> pair = map.get(s);
                set.add(pair.getKey());
                // 返回已存在的序列号
                return pair.getValue();
            } else {
                // 没有就保存进去，注意赋值编号
                map.put(s, new Pair<>(root, ++idx));
                // 返回序号
                return idx;
            }
        }

    }

//leetcode submit region end(Prohibit modification and deletion)

}
